package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-01 15:11
 **/
public class LeetCode139 {

    public static void main(String[] args) {
        LeetCode139 code = new LeetCode139();
        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
        List<String> strings = Arrays.asList("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa");
        code.wordBreak(s, strings);
    }

    TrieNode root = new TrieNode(null);
    //记录已经递归过的索引,这里必须要使用数组来记录递归过的索引,不然会出现超时,重复的太多
    boolean[] index = new boolean[301];

    public boolean wordBreak(String s, List<String> wordDict) {
        //构建前缀树
        for (String word : wordDict) {
            insert(word);
        }

        //查询
        return dfs(s, 0);
    }

    /**
     * dfs遍历判断s是否可以由前缀树中的单词组成
     */
    boolean dfs(String s, int cur) {
        //cur越界,说明遍历完成,返回true
        if (cur == s.length()) {
            return true;
        }

        //从index数组可以直接判断当前索引是否已经遍历过,遍历过说明该索引不能成功,直接返回false;
        if (index[cur]) {
            return false;
        }

        //记忆当前索引被遍历过,置index[cur] = true
        index[cur] = true;

        TrieNode temp = root;
        for (int i = cur; i < s.length(); i++) {
            char c = s.charAt(i);
            TrieNode trieNode = temp.children.get(c);
            if (trieNode == null) {
                return false;
            }

            if (trieNode.isEnd) {
                if (dfs(s, i + 1)) {
                    return true;
                }
            }

            temp = trieNode;
        }
        return false;
    }

    //将一个word插入到字典树中
    public void insert(String word) {
        int n = word.length();

        TrieNode temp = root;
        for (int i = 0; i < n; i++) {
            char c = word.charAt(i);
            TrieNode node = temp.children.get(c);
            if (node == null) {
                node = new TrieNode(c);
                temp.children.put(c, node);
            }
            temp = node;
        }
        temp.isEnd = true;
    }

    //字典树节点
    class TrieNode {
        Character c;
        Map<Character, TrieNode> children;
        boolean isEnd;

        TrieNode(Character c) {
            children = new HashMap<>();
            this.c = c;
        }
    }
}

